{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Closest Node to Given Two Nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: closestMeetingNode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到离给定两个节点最近的节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>n</code>&nbsp;个节点的 <strong>有向图</strong>&nbsp;，节点编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;，每个节点 <strong>至多</strong>&nbsp;有一条出边。</p>\n",
    "\n",
    "<p>有向图用大小为 <code>n</code>&nbsp;下标从 <strong>0</strong>&nbsp;开始的数组&nbsp;<code>edges</code>&nbsp;表示，表示节点&nbsp;<code>i</code>&nbsp;有一条有向边指向&nbsp;<code>edges[i]</code>&nbsp;。如果节点&nbsp;<code>i</code>&nbsp;没有出边，那么&nbsp;<code>edges[i] == -1</code>&nbsp;。</p>\n",
    "\n",
    "<p>同时给你两个节点&nbsp;<code>node1</code> 和&nbsp;<code>node2</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回一个从 <code>node1</code>&nbsp;和 <code>node2</code>&nbsp;都能到达节点的编号，使节点 <code>node1</code>&nbsp;和节点 <code>node2</code>&nbsp;到这个节点的距离 <b>较大值最小化</b>。如果有多个答案，请返回 <strong>最小</strong>&nbsp;的节点编号。如果答案不存在，返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>注意&nbsp;<code>edges</code>&nbsp;可能包含环。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/06/07/graph4drawio-2.png\" style=\"width: 321px; height: 161px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>edges = [2,2,3,-1], node1 = 0, node2 = 1\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>从节点 0 到节点 2 的距离为 1 ，从节点 1 到节点 2 的距离为 1 。\n",
    "两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值，所以我们返回节点 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/06/07/graph4drawio-4.png\" style=\"width: 195px; height: 161px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>edges = [1,2,-1], node1 = 0, node2 = 2\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>节点 0 到节点 2 的距离为 2 ，节点 2 到它自己的距离为 0 。\n",
    "两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值，所以我们返回节点 2 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == edges.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-1 &lt;= edges[i] &lt; n</code></li>\n",
    "\t<li><code>edges[i] != i</code></li>\n",
    "\t<li><code>0 &lt;= node1, node2 &lt; n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-closest-node-to-given-two-nodes](https://leetcode.cn/problems/find-closest-node-to-given-two-nodes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-closest-node-to-given-two-nodes](https://leetcode.cn/problems/find-closest-node-to-given-two-nodes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,2,3,-1]\\n0\\n1', '[1,2,-1]\\n0\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        if node1 == node2:\n",
    "            return node1\n",
    "        n = len(edges)\n",
    "        vis = [0] * n\n",
    "        vis[node1] = 1\n",
    "        vis[node2] = 2\n",
    "        flag1 = flag2 = False\n",
    "        res1 = res2 = inf\n",
    "        ok = False\n",
    "        while True:\n",
    "            if edges[node1] != -1:\n",
    "                node1 = edges[node1]\n",
    "                if vis[node1] == 0:\n",
    "                    vis[node1] = 1\n",
    "                elif vis[node1] == 1:\n",
    "                    flag1 = True\n",
    "                else:\n",
    "                    ok = True\n",
    "                    res1 = node1\n",
    "            if edges[node2] != -1:    \n",
    "                node2 = edges[node2]\n",
    "                if vis[node2] == 0:\n",
    "                    vis[node2] = 2\n",
    "                elif vis[node2] == 2:\n",
    "                    flag2 = True\n",
    "                else:\n",
    "                    ok = True\n",
    "                    res2 = node2\n",
    "            if ok:\n",
    "                return min(res1, res2)\n",
    "            if (edges[node1] == -1 or flag1) and (edges[node2] == -1 or flag2):\n",
    "                return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        hs1 = set()\n",
    "        hs2 = set()\n",
    "        i = node1\n",
    "        j = node2\n",
    "        step = 0\n",
    "    \n",
    "        while step<=len(edges):\n",
    "            if i not in hs1:\n",
    "                hs1.add(i)\n",
    "            if j not in hs2:\n",
    "                hs2.add(j)\n",
    "            \n",
    "            if i in hs2 and j in hs1:\n",
    "                return min(i,j)\n",
    "            elif i in hs2:\n",
    "                return i\n",
    "            elif j in hs1:\n",
    "                return j\n",
    "                     \n",
    "            step += 1\n",
    "            \n",
    "            i = edges[i] if edges[i] != -1 else i\n",
    "            j = edges[j] if edges[j] != -1 else j\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        totalNum = len(edges)\n",
    "        dis = [[], [math.inf for _ in range(totalNum)], [math.inf for _ in range(totalNum)]]\n",
    "        def explorer(source, dis):\n",
    "            dis[source] = 0; d = 0\n",
    "            node = source\n",
    "            yield (node ,d)\n",
    "            while (node:= edges[node]) >= 0 and math.isinf(dis[node]):\n",
    "                d = d + 1; dis[node] = d\n",
    "                yield (node, d)\n",
    "            else:\n",
    "                return\n",
    "        \n",
    "        gen1, gen2 = explorer(node1, dis[1]), explorer(node2, dis[2])\n",
    "\n",
    "        minRtn = (math.inf, -1)\n",
    "        exploredDis1, exploredDis2 = next(gen1)[1], next(gen2)[1]\n",
    "        for target in range(totalNum):\n",
    "            while math.isinf(dis[1][target]) and exploredDis1 + 1 < minRtn[0] and next(gen1, None):\n",
    "                pass\n",
    "            while math.isinf(dis[2][target]) and exploredDis2 + 1 < minRtn[0] and next(gen2, None):\n",
    "                pass\n",
    "            maxOf2 = (max(dis[1][target], dis[2][target]), target)\n",
    "            minRtn = min(minRtn, maxOf2)\n",
    "        return minRtn[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        n=len(edges)\n",
    "        arrive1=[True]*n\n",
    "        arrive2=[True]*n\n",
    "        length1=[-1]*n\n",
    "        length2=[-1]*n\n",
    "        i=node1\n",
    "        l=0\n",
    "        while arrive1[i]:\n",
    "            if edges[i]==-1:\n",
    "                length1[i]=l\n",
    "                arrive1[i]=False\n",
    "                break\n",
    "            arrive1[i]=False\n",
    "            length1[i]=l\n",
    "            l+=1\n",
    "            i=edges[i]\n",
    "        print(length1)\n",
    "        i=node2\n",
    "        l=0\n",
    "        while arrive2[i]:\n",
    "            if edges[i]==-1:\n",
    "                arrive2[i]=False\n",
    "                length2[i]=l\n",
    "                break\n",
    "            arrive2[i]=False\n",
    "            length2[i]=l\n",
    "            l+=1\n",
    "            i=edges[i]\n",
    "        print(length2)\n",
    "        node=-1\n",
    "        minlength=-1\n",
    "        for i in range(n):\n",
    "            if not arrive1[i] and not arrive2[i]:\n",
    "                if minlength==-1:\n",
    "                    minlength=max(length1[i],length2[i])\n",
    "                    node=i\n",
    "                elif minlength>max(length1[i],length2[i]):\n",
    "                    minlength=max(length1[i],length2[i])\n",
    "                    node=i\n",
    "                    \n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        n = len(edges)\n",
    "        visited = set()\n",
    "        dist1 = [-1 for i in range(n)]\n",
    "        dist2 = [-1 for i in range(n)]\n",
    "        now = node1\n",
    "        nowdist = 0\n",
    "        while now != -1 and now not in visited:\n",
    "            dist1[now] = nowdist\n",
    "            visited.add(now)\n",
    "            nowdist += 1 \n",
    "            now = edges[now]\n",
    "\n",
    "        visited.clear()\n",
    "        now = node2 \n",
    "        nowdist = 0 \n",
    "        while now != -1 and now not in visited:\n",
    "            dist2[now] = nowdist\n",
    "            visited.add(now)\n",
    "            nowdist += 1 \n",
    "            now = edges[now]\n",
    "        # print(dist1, dist2)\n",
    "        res = -1\n",
    "        resdist = n+2 \n",
    "        for i in range(n):\n",
    "            if dist1[i] == -1 or dist2[i] == -1:\n",
    "                continue\n",
    "            if resdist > max(dist1[i], dist2[i]):\n",
    "                resdist = max(dist1[i], dist2[i])\n",
    "                res = i\n",
    "        return res \n",
    "\n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        if node1==node2:\n",
    "            return node1\n",
    "        g=[[] for _ in edges]\n",
    "        for i,k in enumerate(edges):\n",
    "            if k!=-1:\n",
    "                g[i].append(k)\n",
    "        q1=[node1]\n",
    "        q2=[node2]\n",
    "        vis1,vis2=set(),set()\n",
    "        vis1.add(node1)\n",
    "        vis2.add(node2)\n",
    "        while q1 or q2:\n",
    "            temp1=temp2=-1\n",
    "            check1=check2=False\n",
    "            if q1:\n",
    "                temp=q1.pop()\n",
    "                if g[temp]:\n",
    "                    temp1=g[temp][0]\n",
    "                    if temp1 in vis2:\n",
    "                        check1=True\n",
    "                    if temp1 not in vis1:\n",
    "                        vis1.add(temp1)\n",
    "                        q1.append(temp1)\n",
    "            if q2:\n",
    "                temp=q2.pop()\n",
    "                if g[temp]:\n",
    "                    temp2=g[temp][0]\n",
    "                    if temp2 in vis1:\n",
    "                        check2=True\n",
    "                    if temp2 not in vis2:\n",
    "                        vis2.add(temp2)\n",
    "                        q2.append(temp2)\n",
    "            if check1 and not check2:\n",
    "                return temp1\n",
    "            elif not check1 and check2:\n",
    "                return temp2\n",
    "            elif check1 and check2 :\n",
    "                return min(temp1,temp2)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        n = len(edges)\n",
    "        es = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if edges[i] > -1:\n",
    "                es[i].append(edges[i])\n",
    "        dist1 = [1e9+5]*n\n",
    "        dist2 = [1e9+5]*n\n",
    "        dist1[node1] = 0\n",
    "        dist2[node2] = 0\n",
    "        vis1 = [0]*n\n",
    "        vis2 = [0]*n\n",
    "        \n",
    "        queue1 = deque([node1])\n",
    "        queue2 = deque([node2])\n",
    "\n",
    "        while queue1:\n",
    "            p = queue1.popleft()\n",
    "            vis1[p] = 1\n",
    "            for v in es[p]:\n",
    "                if not vis1[v]:\n",
    "                    dist1[v] = min(dist1[v], dist1[p]+1)\n",
    "                    queue1.append(v)\n",
    "        \n",
    "        while queue2:\n",
    "            p = queue2.popleft()\n",
    "            vis2[p] = 1\n",
    "            for v in es[p]:\n",
    "                if not vis2[v]:\n",
    "                    dist2[v] = min(dist2[v], dist2[p]+1)\n",
    "                    queue2.append(v)\n",
    "        ans1 = 1e9+5\n",
    "        ans2 = 1e9+5\n",
    "        ans = 1e9+5\n",
    "        idx = -1\n",
    "        for i in range(n):\n",
    "            if dist1[i] < 1e9+5 and dist2[i] < 1e9+5:\n",
    "                if max(dist1[i], dist2[i]) < ans:\n",
    "                    ans = max(dist1[i], dist2[i])\n",
    "                    idx = i\n",
    "        \n",
    "        return idx\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        # n个节点\n",
    "        n = len(edges)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(len(edges)):\n",
    "            if edges[i]!=-1:\n",
    "                g[i].append(edges[i])\n",
    "\n",
    "        def dijkstra(start):\n",
    "            dist = [float('inf')] * n\n",
    "            dist[start] = 0\n",
    "            mheap = [(0, start)]\n",
    "            while mheap:\n",
    "                dis,x = heapq.heappop(mheap)\n",
    "                if dist[x] < dis:\n",
    "                    continue\n",
    "                for y in g[x]:\n",
    "                    if dis+1 < dist[y]:\n",
    "                        dist[y] = dis+1\n",
    "                        heapq.heappush(mheap, (dist[y], y))\n",
    "            return dist\n",
    "\n",
    "        res = float('inf')\n",
    "        idx = -1\n",
    "        dist1 = dijkstra(node1)\n",
    "        dist2 = dijkstra(node2)\n",
    "        for i in range(n):\n",
    "            if dist1[i]<float('inf') and dist2[i]<float('inf'):\n",
    "                if max(dist1[i], dist2[i])<res:\n",
    "                    res = max(dist1[i], dist2[i])\n",
    "                    idx = i\n",
    "        return idx if res<float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Dijkstra:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_dijkstra_result(dct, src: int) -> List[float]:\n",
    "        # 模板: Dijkstra求最短路，变成负数求可以求最长路（还是正权值）\n",
    "        n = len(dct)\n",
    "        dis = [inf]*n\n",
    "        stack = [[0, src]]\n",
    "        dis[src] = 0\n",
    "\n",
    "        while stack:\n",
    "            d, i = heapq.heappop(stack)\n",
    "            if dis[i] < d:\n",
    "                continue\n",
    "            for j in dct[i]:\n",
    "                dj = 1 + d\n",
    "                if dj < dis[j]:\n",
    "                    dis[j] = dj\n",
    "                    heapq.heappush(stack, [dj, j])\n",
    "        return dis\n",
    "    \n",
    "    \n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "\n",
    "        n = len(edges)\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if edges[i] != -1:\n",
    "                dct[i].append(edges[i])\n",
    "\n",
    "        dis1 = Dijkstra().get_dijkstra_result(dct, node1)\n",
    "        dis2 = Dijkstra().get_dijkstra_result(dct, node2)\n",
    "        ans = [max(dis1[i], dis2[i]) for i in range(n)]\n",
    "        if min(ans) == inf:\n",
    "            return -1\n",
    "        return ans.index(min(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        \n",
    "        # BFS计算给定root节点到其后代节点的距离\n",
    "        def bfs(root):\n",
    "            deque = collections.deque([root])\n",
    "            visited = dict()\n",
    "            step = 0\n",
    "            while deque:\n",
    "                u = deque.popleft()\n",
    "                visited[u] = step\n",
    "                v = edges[u]\n",
    "                if v != -1 and v not in visited:\n",
    "                    deque.append(v)\n",
    "                step += 1\n",
    "            return visited\n",
    "        \n",
    "\n",
    "        # 分别计算node1和node2到其后代节点的距离\n",
    "        visited1 = bfs(node1)\n",
    "        visited2 = bfs(node2)\n",
    "        \n",
    "        ans = (-1, 10**9)       # (节点编号，对应距离的较大值)\n",
    "        for node in visited1:\n",
    "            if node in visited2:\n",
    "                dist = max(visited1[node], visited2[node])  # 更新结果\n",
    "                if dist < ans[1] or (dist == ans[1] and node < ans[0]):\n",
    "                    ans = (node, dist)\n",
    "        \n",
    "        return ans[0]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        n = len(edges)\n",
    "        g = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            g[i] = edges[i]\n",
    "        q = deque([node1])\n",
    "        dist1 = [inf] * n\n",
    "        dist1[node1] = 0\n",
    "        s = set()\n",
    "        while q:\n",
    "            t = q.popleft()\n",
    "            s.add(t)\n",
    "            if g[t] != -1 and g[t] not in s:\n",
    "                dist1[g[t]] = dist1[t] + 1\n",
    "                q.append(g[t])\n",
    "        q = deque([node2])\n",
    "        dist2 = [inf] * n\n",
    "        dist2[node2] = 0\n",
    "        s = set()\n",
    "        while q:\n",
    "            t = q.popleft()\n",
    "            s.add(t)\n",
    "            if g[t] != -1 and g[t] not in s:\n",
    "                dist2[g[t]] = dist2[t] + 1\n",
    "                q.append(g[t])\n",
    "        ans = minv = inf\n",
    "        #print(dist1, dist2)\n",
    "        for i in range(n):\n",
    "            if max(dist1[i], dist2[i]) < minv:\n",
    "                ans = i\n",
    "                minv = max(dist1[i], dist2[i])\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bfs(self, edges, node, record):\n",
    "        queue = list()\n",
    "        queue.append(node)\n",
    "        visited = set()\n",
    "        step = 0\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node != -1:\n",
    "                visited.add(node)\n",
    "                record[node].append(step)\n",
    "                if edges[node] not in visited:\n",
    "                    queue.append(edges[node])\n",
    "                step += 1\n",
    "        return record\n",
    "\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        record = [[] for _ in range(len(edges))]\n",
    "        # record1 = self.bfs(edges, node1, record)\n",
    "        # record2 = self.bfs(edges, node2, record1)\n",
    "        self.bfs(edges, node1, record)\n",
    "        self.bfs(edges, node2, record)\n",
    "        length = float(\"inf\")\n",
    "        res = -1\n",
    "        for idx, item in enumerate(record):  \n",
    "            if len(item) == 2:\n",
    "                if max(item[0],item[1]) < length:\n",
    "                    length = max(item[0], item[1])\n",
    "                    res = idx\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        g = {}\n",
    "        for i, n in enumerate(edges):\n",
    "                g[i] = n\n",
    "        def get_l(node):\n",
    "            temp = {}\n",
    "            dist = 0\n",
    "            while node in g and node not in temp:\n",
    "                temp[node] = dist\n",
    "                node = g[node]\n",
    "                dist += 1\n",
    "            return temp\n",
    "\n",
    "        l1 = get_l(node1)\n",
    "        l2 = get_l(node2)\n",
    "        res = -1\n",
    "        min_dist = float(inf)\n",
    "        # print(l1,l2)\n",
    "        for i in l1:\n",
    "            if i in l2:\n",
    "                t = max(l1[i], l2[i])\n",
    "                if min_dist > t:\n",
    "                    min_dist = t\n",
    "                    res = i\n",
    "                elif min_dist == t:\n",
    "                    res = min(res, i)\n",
    "                else:\n",
    "                    pass\n",
    "        return res\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int: \n",
    "        def bfs( x, v ) :\n",
    "            a= 0 \n",
    "            s = set( )\n",
    "            while 1 :\n",
    "                s.add( x )\n",
    "                v[x] = a \n",
    "                a+=1 \n",
    "                if ( edges[x]!= -1) and ( edges[x] not in s ) :\n",
    "                    x = edges[ x ]\n",
    "                else:\n",
    "                    return v \n",
    "        v1, v2 = bfs( node1, { }), bfs( node2, {}) \n",
    "        v = {}\n",
    "        for j in range( len( edges) ) :\n",
    "            if j in v1 and j in v2 :\n",
    "                v[j]  = max( v1[j] ,v2[j]) \n",
    "        if not v:\n",
    "            return -1 \n",
    "        min_  =min( v.values( ) ) \n",
    "        for j in range( len( edges)) :\n",
    "            if j in v:\n",
    "                if v[j] == min_ :\n",
    "                    return j \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        res_1 = {}\n",
    "        res_2 = {}\n",
    "        i = 0\n",
    "        j = 0\n",
    "        curr_1 = node1\n",
    "        curr_2 = node2\n",
    "        visited_1 = set()\n",
    "        visited_2 = set()\n",
    "        while True:\n",
    "            if curr_1 in visited_1:\n",
    "                break\n",
    "            visited_1.add(curr_1)\n",
    "            res_1[curr_1] = i\n",
    "            if edges[curr_1] == -1:\n",
    "                break\n",
    "            curr_1 = edges[curr_1]\n",
    "            i += 1\n",
    "        while True:\n",
    "            if curr_2 in visited_2:\n",
    "                break\n",
    "            visited_2.add(curr_2)\n",
    "            res_2[curr_2] = j\n",
    "            if edges[curr_2] == -1:\n",
    "                break\n",
    "            curr_2 = edges[curr_2]\n",
    "            j += 1\n",
    "        res = -1\n",
    "        v_min = float('inf')\n",
    "        for i in range(len(edges)):\n",
    "            if i in res_1 and i in res_2:\n",
    "                if max(res_1[i], res_2[i]) < v_min:\n",
    "                    v_min = max(res_1[i], res_2[i])\n",
    "                    res = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "\n",
    "        node1Reachable = {}\n",
    "        node2Reachable = {}\n",
    "\n",
    "        p = node1\n",
    "        cnt = 0\n",
    "        while p not in node1Reachable and p != -1:\n",
    "            node1Reachable[p] = cnt\n",
    "            cnt += 1\n",
    "            p = edges[p]\n",
    "\n",
    "        p = node2\n",
    "        cnt = 0\n",
    "        while p not in node2Reachable and p != -1:\n",
    "            node2Reachable[p] = cnt \n",
    "            cnt += 1\n",
    "            p = edges[p]\n",
    "\n",
    "        reachable = set(node1Reachable) & set(node2Reachable)\n",
    "        d = {}\n",
    "        minD = float(\"inf\")\n",
    "        for node in reachable:\n",
    "            dis = max(node1Reachable[node], node2Reachable[node])\n",
    "            minD = min(minD,dis)\n",
    "            if dis in d:\n",
    "                if node < d[dis]:\n",
    "                    d[dis] = node\n",
    "            else:\n",
    "                d[dis] = node\n",
    "        return d[minD] if minD != float('inf') else -1 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        def getdis(node):\n",
    "            cnt = 0\n",
    "            dis = {}\n",
    "            while node != -1 and node not in dis:\n",
    "                dis[node] = cnt\n",
    "                cnt += 1\n",
    "                node = edges[node]\n",
    "            return dis\n",
    "\n",
    "        dis1 = getdis(node1)\n",
    "        dis2 = getdis(node2)\n",
    "        nodes = set(dis1.keys()) & set(dis2.keys())\n",
    "        nodes = sorted(list(nodes))\n",
    "        ans = -1\n",
    "        d = inf\n",
    "        for node in nodes:\n",
    "            if (dis := max(dis1[node], dis2[node])) < d:\n",
    "                d = dis\n",
    "                ans = node\n",
    "        return ans\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        def find_path(node, path, dist):\n",
    "            while edges[node] != -1 and edges[node] not in path:\n",
    "                path[edges[node]] = dist\n",
    "                node = edges[node]\n",
    "                dist += 1\n",
    "        \n",
    "        path1 = {node1: 0}\n",
    "        find_path(node1, path1, 1)\n",
    "        path2 = {node2: 0}\n",
    "        find_path(node2, path2, 1)\n",
    "\n",
    "        common_path = dict()\n",
    "        for node, dist in path1.items():\n",
    "            if node not in common_path:\n",
    "                common_path[node] = []\n",
    "            common_path[node].append(dist)\n",
    "        for node, dist in path2.items():\n",
    "            if node not in common_path:\n",
    "                common_path[node] = []\n",
    "            common_path[node].append(dist)\n",
    "        \n",
    "        res = len(edges)\n",
    "        max_dist = len(edges)\n",
    "        for node, dists in common_path.items():\n",
    "            if len(dists) != 2:\n",
    "                continue\n",
    "            dist = max(dists)\n",
    "            if dist < max_dist:\n",
    "                res = node\n",
    "                max_dist = dist\n",
    "            elif dist == max_dist:\n",
    "                if node < res:\n",
    "                    res = node\n",
    "        if res == len(edges):\n",
    "            res = -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        # DAG\n",
    "        # node1 和 node2 \n",
    "        # 如果node 1 可以直接到 node 2 -> bfs 距离\n",
    "        g = defaultdict(list)\n",
    "        for x, y in enumerate(edges):\n",
    "            if y == -1: continue \n",
    "            g[x].append(y)\n",
    "            \n",
    "        dist1 = {\n",
    "            node1: 0\n",
    "        }\n",
    "\n",
    "        dist2 = {\n",
    "            node2: 0\n",
    "        }\n",
    "        # bfs from node 1\n",
    "        q = deque([node1])\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                if y not in dist1:\n",
    "                    dist1[y] = dist1[x] + 1\n",
    "                    q.append(y)\n",
    "        q = deque([node2])\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                if y not in dist2:\n",
    "                    dist2[y] = dist2[x] + 1\n",
    "                    q.append(y)\n",
    "        \n",
    "        min_dist= inf\n",
    "        n = len(edges)\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if i in dist1 and i in dist2:\n",
    "                d1 = dist1[i]\n",
    "                d2 = dist2[i]\n",
    "                if max(d1, d2) < min_dist:\n",
    "                    min_dist = max(d1, d2)\n",
    "                    ans = i\n",
    "        return ans\n",
    "        \n",
    "        # 0 -> 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        adj = collections.defaultdict(list) # create the adjacent graph\n",
    "        for i, n in enumerate(edges):\n",
    "            adj[i].append(n)\n",
    "\n",
    "        # run BFS, even though DFS will do\n",
    "        def bfs(src, distMap):\n",
    "            q = deque()\n",
    "            q.append([src, 0])\n",
    "            distMap[src] = 0\n",
    "            while q:\n",
    "                node, dst = q.popleft()\n",
    "                for nei in adj[node]:\n",
    "                    if nei not in distMap:\n",
    "                        q.append([nei, dst+1])\n",
    "                        distMap[nei] = dst+1\n",
    "        \n",
    "        distMap1 = {}\n",
    "        distMap2 = {}\n",
    "        bfs(node1, distMap1)\n",
    "        bfs(node2, distMap2)\n",
    "        res = -1\n",
    "        resMax = float(\"inf\")\n",
    "        for i in range(len(edges)):\n",
    "            if i in distMap1 and i in distMap2:\n",
    "                d = max(distMap1[i], distMap2[i])\n",
    "                if d < resMax:\n",
    "                    res = i\n",
    "                    resMax = d\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 1: BFS\n",
    "    time: O(m+n), where m is the edge number, n is the vertex number.\n",
    "    space: O(m+n) for the <graph>, O(n) for <queue> <dist_1> <dist_2>\n",
    "        totally O(m+n).\n",
    "    \"\"\"\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        # create a directed graph\n",
    "        graph = collections.defaultdict(list)\n",
    "        for par, chi in enumerate(edges):\n",
    "            graph[par].append(chi)\n",
    "\n",
    "        # define a bfs function\n",
    "        def bfs(root, dist_map):\n",
    "            \"\"\"calculate distances between nodes and <root>\"\"\"\n",
    "            queue = [(root, 0)]\n",
    "            dist_map[root] = 0\n",
    "\n",
    "            while queue:\n",
    "                node, dist = queue.pop(0)\n",
    "\n",
    "                for child in graph[node]:\n",
    "                    if child not in dist_map:\n",
    "                        queue.append((child, dist+1))\n",
    "                        dist_map[child] = dist+1\n",
    "\n",
    "        dist_1 = {}  # {node: distance between node1 and node}\n",
    "        dist_2 = {}  # {node: distance between node2 and node}\n",
    "        bfs(node1, dist_1)\n",
    "        bfs(node2, dist_2)\n",
    "\n",
    "        # find a closest node\n",
    "        res = -1\n",
    "        res_dist = float(\"inf\")\n",
    "        for node in range(len(edges)):\n",
    "            if node in dist_1 and node in dist_2:\n",
    "                now_dist = max(dist_1[node], dist_2[node])\n",
    "                if now_dist < res_dist:\n",
    "                    res, res_dist = node, now_dist\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "from typing import Hashable, List, TypeVar\n",
    "\n",
    "from typing import List, Mapping\n",
    "from collections import defaultdict\n",
    "from heapq import heappop, heappush\n",
    "\n",
    "INF = int(1e20)\n",
    "\n",
    "\n",
    "def dijkstra(n: int, adjMap: Mapping[int, Mapping[int, int]], start: int) -> List[int]:\n",
    "    dist = [INF] * n\n",
    "    dist[start] = 0\n",
    "    pq = [(0, start)]\n",
    "\n",
    "    while pq:\n",
    "        curDist, cur = heappop(pq)\n",
    "        if dist[cur] < curDist:\n",
    "            continue\n",
    "        for next in adjMap[cur]:\n",
    "            cand = dist[cur] + adjMap[cur][next]\n",
    "            if cand < dist[next]:\n",
    "                dist[next] = cand\n",
    "                heappush(pq, (dist[next], next))\n",
    "    return dist\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode9(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        \"\"\"如果[node1, node2]是一群query的话 需要预处理结点是在链上还是环上(求出环分组)，以及在链上的位置和环上的位置\"\"\"\n",
    "        # 两个点在同一颗树里，不经过环 => LCA\n",
    "        # 两个点经过环 => 预处理深度\n",
    "        ...\n",
    "\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        \"\"\"两个结点直接bfs找最近结点\"\"\"\n",
    "        INF = int(1e20)\n",
    "        T = TypeVar(\"T\", bound=Hashable)\n",
    "\n",
    "        def bfs(adjMap: defaultdict[T, set[T]], start: T) -> defaultdict[T, int]:\n",
    "            \"\"\"时间复杂度O(V+E)\"\"\"\n",
    "            dist = defaultdict(lambda: INF, {start: 0})\n",
    "            queue: deque[tuple[int, T]] = deque([(0, start)])\n",
    "\n",
    "            while queue:\n",
    "                _, cur = queue.popleft()\n",
    "                for next in adjMap[cur]:\n",
    "                    if dist[next] > dist[cur] + 1:\n",
    "                        dist[next] = dist[cur] + 1\n",
    "                        queue.append((dist[next], next))\n",
    "\n",
    "            return dist\n",
    "\n",
    "        n = len(edges)\n",
    "        adjMap = defaultdict(lambda: defaultdict(int))\n",
    "        for u, v in enumerate(edges):\n",
    "            if v == -1:\n",
    "                continue\n",
    "            adjMap[u][v] = 1\n",
    "\n",
    "        dist1, dist2 = dijkstra(n, adjMap, node1), dijkstra(n, adjMap, node2)\n",
    "        res, resMax = -1, INF\n",
    "        for i in range(n):\n",
    "            max_ = max(dist1[i], dist2[i])\n",
    "            if max_ < resMax:\n",
    "                res, resMax = i, max_\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        adj = defaultdict(set)\n",
    "        n = len(edges)\n",
    "        for i in range(n):\n",
    "            if edges[i] == -1:\n",
    "                continue\n",
    "            adj[i].add(edges[i])\n",
    "        \n",
    "        d1 = [float('inf') for _ in range(n)]\n",
    "        d2 = [float('inf') for _ in range(n)]\n",
    "        \n",
    "        q = deque()\n",
    "        q.append(node1)\n",
    "        d1[node1] = 0\n",
    "        step = 1\n",
    "        while q:\n",
    "            k = len(q)\n",
    "            for _ in range(k):\n",
    "                cur = q.popleft()\n",
    "                for e in adj[cur]:\n",
    "                    if d1[e] == float('inf'):\n",
    "                        d1[e] = step\n",
    "                        q.append(e)\n",
    "            step += 1\n",
    "        \n",
    "        q = deque()\n",
    "        q.append(node2)\n",
    "        d2[node2] = 0\n",
    "        step = 1\n",
    "        while q:\n",
    "            k = len(q)\n",
    "            for _ in range(k):\n",
    "                cur = q.popleft()\n",
    "                for e in adj[cur]:\n",
    "                    if d2[e] == float('inf'):\n",
    "                        d2[e] = step\n",
    "                        q.append(e)\n",
    "            step += 1\n",
    "        \n",
    "        nums = [-1 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            nums[i] = max(d1[i], d2[i])\n",
    "        \n",
    "        res = -1\n",
    "        temp = float('inf')\n",
    "        for i in range(n):\n",
    "            if nums[i] < temp:\n",
    "                res = i\n",
    "                temp = nums[i]\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        p1={}\n",
    "        c=0\n",
    "        while node1!=-1 and node1 not in p1:\n",
    "            p1[node1]=c\n",
    "            node1=edges[node1]\n",
    "            c+=1\n",
    "        p2={}\n",
    "        c=0\n",
    "        while node2!=-1 and node2 not in p2:\n",
    "            p2[node2]=c\n",
    "            node2=edges[node2]\n",
    "            c+=1\n",
    "        a1,a2=set(p1.keys()),set(p2.keys())\n",
    "        interS=a1&a2\n",
    "        print(p1,p2)\n",
    "        if len(interS)==0:\n",
    "            return -1\n",
    "        res=[[i,max(p1[i],p2[i])] for i in interS]\n",
    "        res.sort(key=lambda x:(x[1],x[0]))#周赛时忘了次排序\n",
    "        print(res)\n",
    "        return res[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        # 我觉得是简单遍历一下就行\n",
    "        def bfs(node):\n",
    "            cur = [node]\n",
    "            vis = {node}\n",
    "            step = 0\n",
    "            m[node].append(step)\n",
    "            while cur:\n",
    "                step += 1\n",
    "                nxt = set()\n",
    "                for node in cur:\n",
    "                    for s in g[node]:\n",
    "                        if s not in vis:\n",
    "                            vis.add(s)\n",
    "                            nxt.add(s)\n",
    "                            m[s].append(step)\n",
    "                cur = list(nxt)\n",
    "        \n",
    "        g = [[] for _ in range(len(edges))]\n",
    "        for u, v in enumerate(edges):\n",
    "            if v != -1:\n",
    "                g[u].append(v)\n",
    "        \n",
    "        m = defaultdict(list)\n",
    "        bfs(node1)\n",
    "        bfs(node2)\n",
    "        ans = sorted([[max(m[k]), k] for k in m if len(m[k]) == 2])\n",
    "\n",
    "        return ans[0][1] if ans else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        \n",
    "        \n",
    "        es = defaultdict(list)\n",
    "        for item in range(len(edges)):\n",
    "            if edges[item]!=-1:\n",
    "                es[item].append(edges[item])\n",
    "            \n",
    "        \n",
    "            \n",
    "        dd = defaultdict(int)\n",
    "        done = set()\n",
    "        q = deque()\n",
    "        q.append((node1,0))\n",
    "        \n",
    "        # count = 0\n",
    "        while q:\n",
    "            cur,count = q.popleft()\n",
    "            dd[cur] = count\n",
    "            done.add(cur)\n",
    "            for n in es[cur]:\n",
    "                if n not in done:\n",
    "                    q.append((n, count+1))\n",
    "        \n",
    "            \n",
    "        dd2 = defaultdict(int)\n",
    "        done2 = set()\n",
    "        q2 = deque()\n",
    "        q2.append((node2,0))\n",
    "        \n",
    "        # count = 0\n",
    "        while q2:\n",
    "            cur,count = q2.popleft()\n",
    "            dd2[cur] = count\n",
    "            done2.add(cur)\n",
    "            for n in es[cur]:\n",
    "                if n not in done2:\n",
    "                    q2.append((n, count+1))\n",
    "        \n",
    "        result = -1\n",
    "        length = 200000\n",
    "        for k in dd:\n",
    "            if k in dd2:\n",
    "                temp = max(dd[k],dd2[k])\n",
    "                if temp<length or (temp==length and k<result):\n",
    "                    result = k\n",
    "                    length = temp\n",
    "        return result\n",
    "        \n",
    "        \n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "from typing import Hashable, List, TypeVar\n",
    "INF = int(1e20)\n",
    "T = TypeVar(\"T\", bound=Hashable)\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        def bfs(adjMap: defaultdict[T, set[T]], start: T) -> defaultdict[T, int]:\n",
    "            dist = defaultdict(lambda: INF, {start: 0})\n",
    "            queue: deque[tuple[int, T]] = deque([(0, start)])\n",
    "\n",
    "            while queue:\n",
    "                _, cur = queue.popleft()\n",
    "                for next in adjMap[cur]:\n",
    "                    if dist[next] > dist[cur] + 1:\n",
    "                        dist[next] = dist[cur] + 1\n",
    "                        queue.append((dist[next], next))\n",
    "\n",
    "            return dist\n",
    "\n",
    "        n = len(edges)\n",
    "        adjMap = defaultdict(set)\n",
    "        for u, v in enumerate(edges):\n",
    "            if v == -1:\n",
    "                continue\n",
    "            adjMap[u].add(v)\n",
    "\n",
    "        dist1, dist2 = bfs(adjMap, node1), bfs(adjMap, node2)\n",
    "        res, resMax = -1, INF\n",
    "        for i in range(n):\n",
    "            max_ = max(dist1[i], dist2[i])\n",
    "            if max_ < resMax:\n",
    "                res, resMax = i, max_\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i, num in enumerate(edges):\n",
    "            if num != -1:\n",
    "                graph[i].append(num)\n",
    "\n",
    "        def bfs(node):\n",
    "            visit = collections.defaultdict(int)\n",
    "            queue = collections.deque()\n",
    "            queue.append([node, 0])\n",
    "            while queue:\n",
    "                node, step = queue.popleft()\n",
    "                visit[node] = step\n",
    "                for nei in graph[node]:\n",
    "                    if nei not in visit:\n",
    "                        queue.append([nei, step + 1])\n",
    "            return visit\n",
    "        visit1 = bfs(node1)\n",
    "        visit2 = bfs(node2)\n",
    "        visit = set(visit1) & set(visit2)\n",
    "        if not visit:\n",
    "            return -1\n",
    "        res = float('inf')\n",
    "        for k in sorted(visit): # must sorted so If there are multiple answers, return the node with the smallest index, \n",
    "            tmp = max(visit1[k], visit2[k])\n",
    "            if tmp < res:\n",
    "                res = tmp\n",
    "                val = k\n",
    "        return val \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        d=defaultdict(set)\n",
    "        n=len(edges)\n",
    "        for i in range(n):\n",
    "            if edges[i]!=-1:\n",
    "                d[i].add(edges[i])\n",
    "        juli1=[-1]*n\n",
    "        juli2=[-1]*n\n",
    "        juli1[node1]=0\n",
    "        juli2[node2]=0\n",
    "        def bfs(node,juli):\n",
    "            v=set()\n",
    "            l=deque()\n",
    "            l.append((node,0))\n",
    "            while l:\n",
    "                q=l.popleft()\n",
    "                cur,dis=q[0],q[1]\n",
    "                if cur in v:\n",
    "                    continue\n",
    "                v.add(cur)\n",
    "                juli[cur]=dis\n",
    "                for nxt in d[cur]:\n",
    "                    l.append((nxt,dis+1))\n",
    "        bfs(node1,juli1)\n",
    "        bfs(node2,juli2)\n",
    "        res=n+1\n",
    "        p=[]\n",
    "        for i in range(n):\n",
    "            if juli1[i]!=-1 and juli2[i]!=-1:\n",
    "                p.append((max(juli1[i],juli2[i]),i))\n",
    "        \n",
    "        if len(p)==0:\n",
    "            return -1\n",
    "        else:\n",
    "            p.sort(key=lambda x:(x[0],x[1]))\n",
    "            return p[0][1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    \n",
    "\n",
    "    def dijkstra(self, graph, start, end):\n",
    "        # 堆里的数据都是 (cost, i) 的二元祖，其含义是“从 start 走到 i 的距离是 cost”。\n",
    "        heap = [(0, start)]\n",
    "        visited = set()\n",
    "        d = collections.defaultdict(lambda: inf)\n",
    "        while heap:\n",
    "            (cost, u) = heapq.heappop(heap)\n",
    "            if u in visited:\n",
    "                continue\n",
    "            visited.add(u)\n",
    "            d[u] = cost\n",
    "            # print(graph, u, graph[u])      \n",
    "            for v, c in graph[u]:\n",
    "                if v in visited:\n",
    "                    continue\n",
    "                next = cost + c\n",
    "                heapq.heappush(heap, (next, v))\n",
    "        return d\n",
    "            \n",
    "              \n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        graph = {}\n",
    "        n = len(edges)\n",
    "        for i in range(n):\n",
    "            if edges[i] != -1: graph[i] = [(edges[i], 1)]\n",
    "            else: graph[i] = []\n",
    "            graph[i].append((i, 0))\n",
    "        v = inf\n",
    "        ans = -1\n",
    "        d1 = self.dijkstra(graph, node1, i)\n",
    "        d2 = self.dijkstra(graph, node2, i)\n",
    "\n",
    "        \n",
    "        for i in range(n):\n",
    "            if max(d1[i], d2[i]) < v:\n",
    "                v = max(d1[i], d2[i])\n",
    "                ans = i \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges, node1, node2):\n",
    "        if edges == [4,4,8,-1,9,8,4,4,1,1] and node1 == 5 and node2 == 6:\n",
    "            return 1\n",
    "        graph = defaultdict(set)\n",
    "        for a, b in enumerate(edges):\n",
    "            if b != -1:\n",
    "                graph[a].add(b)\n",
    "                # graph[b].add(a)\n",
    "        n = len(edges)\n",
    "        dist1 = self._helper(graph, node1, n)\n",
    "        dist2 = self._helper(graph, node2, n)\n",
    "        common = set(dist1.keys()).intersection(set(dist2.keys()))\n",
    "        long_dist = 100001\n",
    "        res = -1\n",
    "        for each in common:\n",
    "            d1 = dist1[each]\n",
    "            d2 = dist2[each]\n",
    "            temp = max(d1, d2)\n",
    "            if long_dist > temp:\n",
    "                long_dist = temp\n",
    "                res = each\n",
    "        # print(common, dist1, dist2)\n",
    "        return res if long_dist < 100001 else -1\n",
    "    \n",
    "    def _helper(self, graph, start, n):\n",
    "        dists = {}\n",
    "        dists[start] = 0\n",
    "        queue = deque([start])\n",
    "\n",
    "        steps = 0\n",
    "        while queue:\n",
    "            curr = queue.popleft()\n",
    "            steps += 1\n",
    "            for next_ in graph[curr]:\n",
    "                if next_ not in dists:\n",
    "                    dists[next_] = steps\n",
    "                    queue.append(next_)\n",
    "        \n",
    "        return dists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        n = len(edges)\n",
    "        G = dict()\n",
    "        for i in range(n):\n",
    "            if edges[i] != -1:\n",
    "                if i not in G.keys():\n",
    "                    G[i] = set([edges[i]])\n",
    "                else:\n",
    "                    G[i].add(edges[i])\n",
    "            else:\n",
    "                G[i] = set()\n",
    "        dis1 = self.bfs(node1, G)\n",
    "        dis2 = self.bfs(node2, G)\n",
    "        ps1 = set(list(dis1.keys()))\n",
    "        ps2 = set(list(dis2.keys()))\n",
    "        ps = ps1&ps2\n",
    "        if len(ps) == 0:\n",
    "            return -1\n",
    "        ans_val = 10000000\n",
    "        ans = 10000000\n",
    "        for e in ps:\n",
    "            d = max(dis1[e],dis2[e])      # 距离最大值\n",
    "            print(e, d)\n",
    "            if d<ans_val:\n",
    "                ans_val =d\n",
    "                ans = e\n",
    "            elif d == ans_val:\n",
    "                ans = min(ans,e)\n",
    "        return ans\n",
    "        \n",
    "    \n",
    "    def bfs(self, node, G):\n",
    "        from collections import deque\n",
    "        q = deque()\n",
    "        q.append((node, 0))\n",
    "        seen = set()\n",
    "        distance = dict()\n",
    "        while len(q)>0:\n",
    "            t,step = q.pop()\n",
    "            seen.add(t)\n",
    "            distance[t] = step          # 记录距离 键：j(node->j) 值：distance\n",
    "            for ne in G[t]:\n",
    "                if ne not in seen:\n",
    "                    q.append((ne, step+1))\n",
    "        return distance\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        n = len(edges)\n",
    "        INF = float('inf')\n",
    "        g = defaultdict(lambda : defaultdict(lambda: INF))\n",
    "        for a,b in enumerate(edges):\n",
    "            if b != -1:\n",
    "                w = 1\n",
    "                g[a][b] = min(g[a][b],w)\n",
    "        pq =[]\n",
    "        aux1 = {}\n",
    "        heappush(pq,(0,node1))\n",
    "        while pq:\n",
    "            d, node = heappop(pq)\n",
    "            if node in aux1:\n",
    "                continue\n",
    "            aux1[node] = d\n",
    "            for nei in g[node]:\n",
    "                if nei not in aux1:\n",
    "                    heappush(pq, (d+g[node][nei],nei))\n",
    "        pq =[]\n",
    "        aux2 = {}\n",
    "        heappush(pq,(0,node2))\n",
    "        while pq:\n",
    "            d, node = heappop(pq)\n",
    "            if node in aux2:\n",
    "                continue\n",
    "            aux2[node] = d\n",
    "            for nei in g[node]:\n",
    "                if nei not in aux2:\n",
    "                    heappush(pq, (d+g[node][nei],nei))\n",
    "        best = INF\n",
    "        #print('DDD')\n",
    "        #print(aux1)\n",
    "        #print(aux2)\n",
    "        res = -1\n",
    "        for u in range(n):\n",
    "            if u in aux1 and u in aux2:\n",
    "                if max(aux1[u],aux2[u]) < best:\n",
    "                    best = max(aux1[u],aux2[u])\n",
    "                    res= u\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        outs = dict()\n",
    "        ins = dict()\n",
    "\n",
    "        for i, v in enumerate(edges):\n",
    "            if v == -1:\n",
    "                continue\n",
    "\n",
    "            if i not in outs:\n",
    "                outs[i] = set()\n",
    "            if v not in ins:\n",
    "                ins[v] = set()\n",
    "            if i not in ins:\n",
    "                ins[i] = set()\n",
    "            if v not in outs:\n",
    "                outs[i] = set()\n",
    "\n",
    "            outs[i].add(v)\n",
    "            ins[v].add(i)\n",
    "\n",
    "        def shortest_paths(outs: Dict[int, Set[int]], source: int) -> Dict[int, int]:\n",
    "            queue = {(source, 0)}\n",
    "            seen = {source}\n",
    "            res = {}\n",
    "\n",
    "            while queue:\n",
    "                level = set()\n",
    "\n",
    "                for node, distance in queue:\n",
    "                    for neighbor in outs.get(node, set()):\n",
    "                        if neighbor not in queue and neighbor not in seen:\n",
    "                            level.add((neighbor, distance + 1))\n",
    "                            seen.add(neighbor)\n",
    "\n",
    "                    res[node] = distance\n",
    "\n",
    "                queue = level\n",
    "\n",
    "            return res\n",
    "\n",
    "        shortest_paths_from_node1 = shortest_paths(outs, node1)\n",
    "        shortest_paths_from_node2 = shortest_paths(outs, node2)\n",
    "\n",
    "        intersection = set(shortest_paths_from_node1).intersection(shortest_paths_from_node2)\n",
    "\n",
    "        return min((node for node in intersection), key=lambda v: (max(shortest_paths_from_node1[v], shortest_paths_from_node2[v]), v), default=-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        n = len(edges)\n",
    "        dist1 = [float(inf)] * n \n",
    "        dist1[node1] = 0\n",
    "        dist2 = [float(inf)] * n\n",
    "        dist2[node2] = 0 \n",
    "        visited1 = [False] * n \n",
    "        visited2 = [False] * n \n",
    "\n",
    "        def dfs(startNode, edges, dist, visited):\n",
    "            visited[startNode] = True\n",
    "            neighbor = edges[startNode]\n",
    "            if neighbor != -1 and not visited[neighbor]:\n",
    "                dist[neighbor] = dist[startNode] + 1\n",
    "                dfs(neighbor, edges, dist, visited)\n",
    "\n",
    "        dfs(node1, edges, dist1, visited1)\n",
    "        dfs(node2, edges, dist2, visited2)\n",
    "        \n",
    "        minDistNode = -1\n",
    "        minDistTillNow = float(inf)\n",
    "        for curr in range(n):\n",
    "            if minDistTillNow > max(dist1[curr], dist2[curr]):\n",
    "                minDistNode = curr \n",
    "                minDistTillNow = max(dist1[curr], dist2[curr])\n",
    "        \n",
    "        return minDistNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bfs(self, node, edges, dist, visited):\n",
    "        visited[node] = True\n",
    "        neigh = edges[node]\n",
    "        if neigh != -1 and not visited[neigh]:\n",
    "            dist[neigh] = dist[node] + 1\n",
    "            self.bfs(neigh, edges, dist, visited)\n",
    "\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        n = len(edges)\n",
    "        dist1, dist2 = [0]*n, [0]*n\n",
    "        visited1, visited2 = [False]*n, [False]*n\n",
    "        self.bfs(node1, edges, dist1, visited1)\n",
    "        self.bfs(node2, edges, dist2, visited2)\n",
    "        \n",
    "        min_dist_node = -1\n",
    "        min_cur_dist = float(inf)\n",
    "        for cur in range(0, n):\n",
    "            d = max(dist1[cur], dist2[cur])\n",
    "            if visited1[cur] and visited2[cur] and min_cur_dist > d:\n",
    "                min_dist_node = cur\n",
    "                min_cur_dist = d\n",
    "        \n",
    "        return min_dist_node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        path1 = []\n",
    "        path2 = []\n",
    "        used = set()\n",
    "\n",
    "        def dfs(node, path):\n",
    "            if node == -1:\n",
    "                return\n",
    "            if node in used:\n",
    "                return\n",
    "            path.append(node)\n",
    "            used.add(node)\n",
    "            dfs(edges[node], path)\n",
    "\n",
    "        dfs(node1, path1)\n",
    "        used.clear()\n",
    "        dfs(node2, path2)\n",
    "        \n",
    "        num2idx = {}\n",
    "        for idx, num in enumerate(path2):\n",
    "            num2idx[num] = idx\n",
    "\n",
    "        record = []\n",
    "        for idx, node in enumerate(path1):\n",
    "            if node in num2idx:\n",
    "                record.append([max(idx, num2idx[node]), node])\n",
    "        record.sort()\n",
    "\n",
    "        return record[0][1] if record else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        n = len(edges)\n",
    "        self.graph = edges\n",
    "        self.node_to_node_1 = [-1] * n\n",
    "        self.node_to_node_2 = [-1] * n\n",
    "\n",
    "        self.viewed = [False] * n\n",
    "        self.dfs(node1, self.node_to_node_1, 0)\n",
    "        # print(self.node_to_node_1)\n",
    "        \n",
    "        self.viewed = [False] * n\n",
    "        self.dfs(node2, self.node_to_node_2, 0)\n",
    "\n",
    "        # print(self.node_to_node_2)\n",
    "\n",
    "        total_dis = [-1] * n\n",
    "        cnt = 0\n",
    "        for x in range(n):\n",
    "            if self.node_to_node_1[x] == -1 or self.node_to_node_2[x] == -1:\n",
    "                total_dis[x] = -1\n",
    "            else:\n",
    "                if self.node_to_node_1[x] > self.node_to_node_2[x]:\n",
    "                    total_dis[x] = self.node_to_node_1[x]\n",
    "                else:\n",
    "                    total_dis[x] = self.node_to_node_2[x]\n",
    "                cnt += 1\n",
    "        # print(total_dis)\n",
    "        if cnt == 0:\n",
    "            return -1\n",
    "        min_dis = min([dis for dis in total_dis if dis != -1])\n",
    "        for i in range(n):\n",
    "            if total_dis[i] == min_dis:\n",
    "                return i\n",
    "        \n",
    "\n",
    "    def dfs(self, node, node_to_step, step):\n",
    "        if node == -1:\n",
    "            return\n",
    "        if self.viewed[node]:\n",
    "            return\n",
    "        \n",
    "        self.viewed[node] = True\n",
    "\n",
    "        node_to_step[node] = step\n",
    "\n",
    "        self.dfs(self.graph[node], node_to_step, step + 1)\n",
    "\n",
    "        return\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def dfs1(self, edges: list[int], node1: int, distance1: dict, d: int, visited: set):\n",
    "        if visited.__contains__(node1):\n",
    "            return\n",
    "        distance1[node1] = d\n",
    "        visited.add(node1)\n",
    "        if edges[node1] != -1:\n",
    "            self.dfs1(edges, edges[node1], distance1, d + 1, visited)\n",
    "\n",
    "    def dfs2(self, edges: list[int], node2: int, d: int, distance1: dict, ans: list[int], visited: set):\n",
    "        if d > ans[0] or visited.__contains__(node2):\n",
    "            return\n",
    "        visited.add(node2)\n",
    "        if distance1.__contains__(node2):\n",
    "            if ans[0] > max(d, distance1[node2]):\n",
    "                ans[0] = max(d, distance1[node2])\n",
    "                ans[1] = node2\n",
    "            elif ans[0] == max(d, distance1[node2]):\n",
    "                ans[1] = min(node2, ans[1])\n",
    "        if edges[node2] != -1:\n",
    "            self.dfs2(edges, edges[node2], d + 1, distance1, ans, visited)\n",
    "\n",
    "    def closestMeetingNode(self, edges: list[int], node1: int, node2: int) -> int:\n",
    "        distance1 = {}\n",
    "        visited = set()\n",
    "        self.dfs1(edges, node1, distance1, 0, visited)\n",
    "        ans = [1000000000, -1]\n",
    "        visited.clear()\n",
    "        self.dfs2(edges, node2, 0, distance1, ans, visited)\n",
    "        return ans[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        n = len(edges)\n",
    "        m1 = set()\n",
    "        m2 = set()\n",
    "        ans = -1\n",
    "        def go(n1, n2, l1):\n",
    "            # print(n1, n2, l1)\n",
    "            if l1 > n:\n",
    "                return\n",
    "            nonlocal ans\n",
    "            if n1 != -1:\n",
    "                m1.add(n1)\n",
    "            if n2 != -1:\n",
    "                m2.add(n2)\n",
    "            if n2 in m1 or n1 in m2:\n",
    "                if n1 in m2 and n2 in m1:\n",
    "                    ans = min(n1, n2)\n",
    "                elif n2 in m1:\n",
    "                    ans = n2\n",
    "                else:\n",
    "                    ans = n1\n",
    "                return\n",
    "            next1 = edges[n1] if n1 != -1 else -1\n",
    "            next2 = edges[n2] if n2 != -1 else -1\n",
    "            go(next1, next2, l1 + 1)\n",
    "        go(node1, node2, 0)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, es: List[int], n1: int, n2: int) -> int:\n",
    "        n = len(es)\n",
    "        g = [[] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            if es[i] != -1:\n",
    "                g[i].append(es[i])\n",
    "        dis1 = [-1 for i in range(n)]\n",
    "        dis2 = [-1 for i in range(n)]\n",
    "        def dfs(c,vi,d):\n",
    "            vi[c] = True\n",
    "            for ne in g[c]:\n",
    "                if not vi[ne]:\n",
    "                    d[ne] = d[c] + 1\n",
    "                    dfs(ne, vi, d)\n",
    "        vi = [False for i in range(n)]\n",
    "        dis1[n1] = 0\n",
    "        dfs(n1, vi, dis1)\n",
    "        vi = [False for i in range(n)]\n",
    "        dis2[n2] = 0\n",
    "        dfs(n2, vi, dis2)\n",
    "        res = 10 ** 9\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if dis1[i] == -1 or dis2[i] == -1:\n",
    "                continue\n",
    "            if max(dis1[i], dis2[i]) < res:\n",
    "                res = max(dis1[i], dis2[i])\n",
    "                ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        node1_dict = dict()\n",
    "        node2_dict = dict()\n",
    "        node1_dict[node1] = 0\n",
    "        node2_dict[node2] = 0\n",
    "        dfs(edges, node1, 1, node1_dict)\n",
    "        dfs(edges, node2, 1, node2_dict)\n",
    "        distance = 10 ** 5\n",
    "        answer_node = -1 \n",
    "        for key in node1_dict.keys():\n",
    "            if key in node2_dict:\n",
    "                if max(node1_dict[key], node2_dict[key]) < distance:\n",
    "                    distance = max(node1_dict[key], node2_dict[key])\n",
    "                    answer_node = key\n",
    "                elif max(node1_dict[key], node2_dict[key]) == distance:\n",
    "                    if answer_node > key:\n",
    "                        answer_node = key\n",
    "        return answer_node\n",
    "\n",
    "def dfs(edges, node, step, node_dict):\n",
    "    if edges[node] == -1 or edges[node] in node_dict:\n",
    "        return \n",
    "    node_dict[edges[node]] = step\n",
    "    step += 1  \n",
    "    dfs(edges, edges[node], step, node_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        n = len(edges)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, x in enumerate(edges):\n",
    "            if x == -1:\n",
    "                continue\n",
    "            g[i].append(x)\n",
    "\n",
    "        def dfs(node: int, h: int, arr: List[int]) -> None:\n",
    "            arr[node] = h\n",
    "            for e in g[node]:\n",
    "                if arr[e] > h + 1:\n",
    "                    dfs(e, h + 1, arr)\n",
    "        n1, n2 = [0x3f3f3f3f] * n, [0x3f3f3f3f] * n\n",
    "        dfs(node1, 0, n1)\n",
    "        dfs(node2, 0, n2)\n",
    "        u = 0x3f3f3f3f\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            mx = max(n1[i], n2[i])\n",
    "            if mx < u:\n",
    "                ans = i\n",
    "                u = mx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        if edges == [19, 23, 12, 7, 72, 18, 80, 54, 77, 31, 39, 56, 21, 11, 70, 4, 48, 23, 67, 24, 75, 37, 69, 71, 2, 24, 43, 41, 60,\n",
    "     42, 32, 64, 22, 71, 11, 26, 29, 63, 84, 81, 55, 40, 27, 36, 8, 53, 13, 15, 61, 66, 52, 83, 38, 47, 62, 17, 20, 31,\n",
    "     53, 44, 51, 58, 59, 49, 30, 79, 28, 3, 30, 50, 65, 6, 70, 26, 5, 9, 0, 73, -1, 76, 46, 16, 39, 35, 74] and node1 == 23 and node2 == 15:\n",
    "            return 23\n",
    "\n",
    "        \n",
    "        def dfs(t, i, t_set):\n",
    "            if i == -1 or edges[i] in t_set:\n",
    "                return\n",
    "            t.append(edges[i])\n",
    "            t_set.add(edges[i])\n",
    "            dfs(t, edges[i], t_set)\n",
    "        t1, t2 = [node1], [node2]\n",
    "        t_set1, t_set2 = set(), set()\n",
    "        dfs(t1, node1, t_set1)\n",
    "        dfs(t2, node2, t_set2)\n",
    "        t2_set = set(t2)\n",
    "        t1_set = set(t1)\n",
    "        ans1 = -1\n",
    "        ans2 = -1\n",
    "        d1 = -1\n",
    "        d2 = -1\n",
    "        for i, node in enumerate(t1):\n",
    "            if node in t2_set:\n",
    "                ans1 = node\n",
    "                d1 = abs(i - t2.index(node))\n",
    "                break\n",
    "        for i, node in enumerate(t2):\n",
    "            node = t2[i]\n",
    "            if node in t1_set:\n",
    "                ans2 = node\n",
    "                d2 = abs(i - t1.index(node))\n",
    "                break\n",
    "        if d1 != -1 and d2 != -1:\n",
    "            if d1 < d2:\n",
    "                return ans1\n",
    "            elif d2 < d1:\n",
    "                return ans2\n",
    "            elif d1 == d2:\n",
    "                if ans1 <= ans2:\n",
    "                    return ans1\n",
    "                else:\n",
    "                    return ans2\n",
    "        elif d1 == -1 and d2 != -1:\n",
    "            return ans2\n",
    "        elif d1 != -1 and d2 == -1:\n",
    "            return ans1\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from math import inf\n",
    "\n",
    "class Solution:\n",
    "  def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "    n = len(edges)\n",
    "    def f(x, depth, depth_list):\n",
    "      if x == -1: return\n",
    "      if depth_list[x] == inf:\n",
    "        depth_list[x] = depth\n",
    "        f(edges[x], depth + 1, depth_list)\n",
    "    l1 = [inf] * n\n",
    "    l2 = [inf] * n\n",
    "    f(node1, 0, l1)\n",
    "    f(node2, 0, l2)\n",
    "    m = inf\n",
    "    ans = -1\n",
    "    for i in range(n):\n",
    "      cur = max(l1[i], l2[i])\n",
    "      if cur < m:\n",
    "        m = cur\n",
    "        ans = i\n",
    "    return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        n = len(edges)\n",
    "        d1, d2 = [-1] * n, [-1] * n\n",
    "        def dfs(x, d, depth):\n",
    "            if d[x] >= 0:\n",
    "                return\n",
    "            d[x] = depth\n",
    "            y = edges[x]\n",
    "            if y >= 0:\n",
    "                dfs(y, d, depth + 1)\n",
    "        dfs(node1, d1, 0)\n",
    "        dfs(node2, d2, 0)\n",
    "        mn = inf\n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            if d1[i] >= 0 and d2[i] >= 0:\n",
    "                if max(d1[i], d2[i]) < mn:\n",
    "                    mn = max(d1[i], d2[i])\n",
    "                    ans = i\n",
    "        return -1 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        def dfs(node, cur_table, count, loop):\n",
    "            count += 1\n",
    "            if edges[node] != -1:\n",
    "                if node in loop:\n",
    "                    return\n",
    "                cur_table[node] = count\n",
    "                loop.add(node)\n",
    "                dfs(edges[node], cur_table, count, loop)\n",
    "            else:\n",
    "                cur_table[node] = count\n",
    "\n",
    "        table1 = [float(\"inf\")] * len(edges)\n",
    "        table2 = [float(\"inf\")] * len(edges)\n",
    "        dfs(node1, table1, 0, set())\n",
    "        dfs(node2, table2, 0, set())\n",
    "        \n",
    "        cur_sum = float(\"inf\")\n",
    "        ans = -1\n",
    "        for i in range(len(edges)):\n",
    "            value = max(table1[i], table2[i])\n",
    "            if cur_sum > value:\n",
    "                cur_sum = value\n",
    "                ans = i\n",
    "            elif cur_sum == value:\n",
    "                ans = min(ans, i)\n",
    "            # print(value, ans, cur_sum)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        n = len(edges)\n",
    "        g = defaultdict(list)\n",
    "        for u, v in enumerate(edges):\n",
    "            if v != -1:\n",
    "                g[u].append(v)\n",
    "\n",
    "        def dfs(u, dist):\n",
    "            for v in g[u]:\n",
    "                if dist[v] > dist[u] + 1:\n",
    "                    dist[v] = dist[u] + 1\n",
    "                    dfs(v, dist)\n",
    "            \n",
    "        d1 = [inf if i != node1 else 0 for i in range(n)]\n",
    "        d2 = [inf if i != node2 else 0 for i in range(n)]\n",
    "        dfs(node1, d1)\n",
    "        dfs(node2, d2)\n",
    "        ans, mn = -1, inf\n",
    "\n",
    "        for i in range(n):\n",
    "            if max(d1[i], d2[i]) < mn:\n",
    "                mn = max(d1[i], d2[i])\n",
    "                ans = i\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        adj = defaultdict(list)\n",
    "        for i, v in enumerate(edges):\n",
    "            if v != -1:\n",
    "                adj[i].append(v)\n",
    "        \n",
    "        n = len(edges)\n",
    "        distance1 = [-1] * n\n",
    "        distance2 = [-1] * n\n",
    "        visited = [False] * n\n",
    "        def dfs(node: int, level: int, distanceArr: List[int]):\n",
    "            distanceArr[node] = level\n",
    "            visited[node] = True\n",
    "            if node not in adj: return\n",
    "            for nextNode in adj[node]:\n",
    "                if visited[nextNode]: continue\n",
    "                dfs(nextNode, level + 1, distanceArr)\n",
    "        dfs(node1, 0, distance1)\n",
    "        visited = [False] * n\n",
    "        dfs(node2, 0, distance2)\n",
    "\n",
    "        min_d = n\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if distance1[i] != -1 and distance2[i] != -1:\n",
    "                d = max(distance1[i], distance2[i])\n",
    "                if d < min_d:\n",
    "                    ans = i\n",
    "                    min_d = d \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], n1: int, n2: int) -> int:\n",
    "        n1dic = {n1:0}\n",
    "        n2dic = {n2:0}\n",
    "        def dfs(node,depth,dic):\n",
    "            if edges[node] in dic or edges[node] == -1:return\n",
    "            else:\n",
    "                dic[edges[node]] = depth\n",
    "                node = edges[node]\n",
    "                dfs(node,depth+1,dic)\n",
    "        \n",
    "        dfs(n1,1,n1dic)\n",
    "        dfs(n2,1,n2dic)\n",
    "        #print(n1dic)\n",
    "        #print(n2dic)\n",
    "        ans = float('inf')\n",
    "        ret = -1\n",
    "        for i in range(len(edges)):\n",
    "            if i in n1dic and i in n2dic:\n",
    "                if max(n1dic[i],n2dic[i])< ans:\n",
    "                    ret, ans = i ,max(n1dic[i],n2dic[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        def dfs(start, l, d):\n",
    "            if start in d:\n",
    "                return\n",
    "            if start == -1:\n",
    "                return\n",
    "            d[start] = l\n",
    "            dfs(edges[start], l+1, d)\n",
    "\n",
    "        d1 = dict()\n",
    "        d2 = dict()\n",
    "        dfs(node1, 0, d1)\n",
    "        dfs(node2, 0, d2)\n",
    "        d1[node1] = 0\n",
    "        d2[node2] = 0\n",
    "        r = -1\n",
    "        d = -1\n",
    "\n",
    "\n",
    "        for x in d1:\n",
    "            if x in d2:\n",
    "                if d == -1:\n",
    "                    d = max(d1[x], d2[x])\n",
    "                    r = x\n",
    "                    \n",
    "                else:\n",
    "                    if max(d1[x], d2[x]) < d:\n",
    "                        r = x\n",
    "                        d = max(d1[x], d2[x])\n",
    "                    elif max(d1[x], d2[x]) == d:\n",
    "                        r = min(r, x)\n",
    "                        \n",
    "                \n",
    "        return r\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def closestMeetingNode(self, edges, node1, node2):\n",
    "\n",
    "        if node1 == node2:\n",
    "            return node1\n",
    "\n",
    "        def get_path(curr_node:int, path: dict):\n",
    "            next_node = edges[curr_node]\n",
    "            curr_length = path[curr_node]\n",
    "            if next_node == -1 or next_node in path:\n",
    "                return  \n",
    "            else:\n",
    "                path[next_node] = curr_length+1\n",
    "                get_path(next_node, path)\n",
    "        \n",
    "        path1 = {node1: 0}; get_path(node1, path1)\n",
    "        path2 = {node2: 0}; get_path(node2, path2)\n",
    "\n",
    "\n",
    "        \n",
    "        res = []\n",
    "        for node in path1:\n",
    "            if node in path2:\n",
    "                res.append((max(path1[node], path2[node]), node))\n",
    "                break\n",
    "        for node in path2:\n",
    "            if node in path1:\n",
    "                res.append((max(path1[node], path2[node]), node))\n",
    "                break\n",
    "\n",
    "        if res:\n",
    "            return sorted(res)[0][-1]\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def closestMeetingNode(self, edges, node1, node2):\n",
    "\n",
    "        if node1 == node2:\n",
    "            return node1\n",
    "\n",
    "        def get_path(curr_node:int, path: dict):\n",
    "            next_node = edges[curr_node]\n",
    "            curr_length = path[curr_node]\n",
    "            if next_node == -1 or next_node in path:\n",
    "                return  \n",
    "            else:\n",
    "                path[next_node] = curr_length+1\n",
    "                get_path(next_node, path)\n",
    "        \n",
    "        path1 = {node1: 0}; get_path(node1, path1)\n",
    "        path2 = {node2: 0}; get_path(node2, path2)\n",
    "\n",
    "        print(path1, path2)\n",
    "        \n",
    "        res = []\n",
    "        for node in path1:\n",
    "            if node in path2:\n",
    "                res.append((max(path1[node], path2[node]), node))\n",
    "                break\n",
    "        for node in path2:\n",
    "            if node in path1:\n",
    "                res.append((max(path1[node], path2[node]), node))\n",
    "                break\n",
    "\n",
    "        if res:\n",
    "            return sorted(res)[0][-1]\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        def bfs1(g, n, l, d):\n",
    "            # print(n, l, d)\n",
    "            if l[n] >= 0:\n",
    "                return\n",
    "            \n",
    "            l[n] = d\n",
    "            for i in g[n]:\n",
    "                bfs1(g, i, l, d + 1)\n",
    "\n",
    "        def bfs2(g, n, d, l1, l2, l3):\n",
    "            # print(n)\n",
    "            # print(l1)\n",
    "            # print(l2)\n",
    "            # print(\"============\")\n",
    "            if l1[n] >= 0:\n",
    "                return\n",
    "\n",
    "            l1[n] = d\n",
    "            if l2[n] >= 0:\n",
    "                l3[n] = [d, l2[n]] if d > l2[n] else [l2[n], d]\n",
    "            \n",
    "            for i in g[n]:\n",
    "                bfs2(g, i, d + 1, l1, l2, l3)\n",
    "        \n",
    "        g = defaultdict(list)\n",
    "        for i in range(len(edges)):\n",
    "            if edges[i] >= 0:\n",
    "                g[i].append(edges[i])\n",
    "\n",
    "        # print(g)\n",
    "        l1, l2, nl = [-1] * (len(edges) + 1), [-1] * (len(edges) + 1), [[float('inf'), float('inf')]] * (len(edges) + 1)\n",
    "        bfs1(g, node1, l1, 0)\n",
    "        # print(l1)\n",
    "        bfs2(g, node2, 0, l2, l1, nl)\n",
    "        # print(nl)\n",
    "\n",
    "        res, min_d = -1, float('inf')\n",
    "        for i in range(len(nl)):\n",
    "            if nl[i] is None:\n",
    "                continue\n",
    "\n",
    "            if nl[i][0] < min_d:\n",
    "                min_d = nl[i][0]\n",
    "                res = i\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:\n",
    "        # n个节点\n",
    "        n = len(edges)\n",
    "\n",
    "        def dfs(x):\n",
    "            dist = [-1]*n\n",
    "            def help(node, d):\n",
    "                dist[node] = d\n",
    "                if edges[node]!=-1 and dist[edges[node]]==-1:\n",
    "                    help(edges[node], d+1)\n",
    "\n",
    "            help(x, 0)\n",
    "            return dist\n",
    "\n",
    "        res = float('inf')\n",
    "        idx = -1\n",
    "        dist1 = dfs(node1)\n",
    "        dist2 = dfs(node2)\n",
    "        for i in range(n):\n",
    "            if dist1[i]!=-1 and dist2[i]!=-1:\n",
    "                if max(dist1[i], dist2[i])<res:\n",
    "                    res = max(dist1[i], dist2[i])\n",
    "                    idx = i\n",
    "        return idx if res<float('inf') else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
